package com.likou;

import java.util.*;

/**
 * Author: 陈桂明
 * Date: 2025/4/11 12:53
 * Description: q239
 */
public class q239 {
    public static void main(String[] args) {
        int[] ints = new q239().maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3);
        System.out.println(Arrays.toString(ints));
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> deque = new ArrayDeque<>();
        int l = nums.length;
        int[] ans = new int[l - k + 1];

        for (int i = 0; i < l; i++) {
            while (deque.size() > 0 && nums[i] >= nums[deque.peek()]) {
                deque.pop();
            }

            deque.push(i);
            if (i - k == deque.getLast()) {
                deque.pollLast();
            }

            if (i >= (k - 1)) {
                ans[i - k + 1] = nums[deque.getLast()];
            }
        }

        return ans;
    }

    //
    // public int[] maxSlidingWindow(int[] nums, int k) {
    //     // int left = 0;
    //     // int right = k - 1;
    //     // int[] queue = new int[k];
    //     int i = 0;
    //     int max = 0;
    //     int[] maxList = new int[nums.length - k + 1];
    //     int index = 0;
    //
    //     for (; i < k; i++) {
    //         // queue[k - i - 1] = nums[i];
    //         max = Math.max(max, nums[i]);
    //     }
    //     maxList[index] = max;
    //     index++;
    //
    //     for (; i < nums.length; i++) {
    //         while (i < nums.length && nums[i] >= max) {
    //             maxList[index] = nums[i];
    //             max = nums[i];
    //             i++;
    //             index++;
    //         }
    //
    //         if (i == nums.length) {
    //             return maxList;
    //         }
    //
    //         max = nums[i];
    //         for (int j = 0; j < k; j++) {
    //             // queue[k - j - 1] = nums[i - k + 1 + j];
    //             max = Math.max(max, nums[i - k + 1 + j]);
    //         }
    //         maxList[index] = max;
    //         index++;
    //         // max = nums[i];
    //         // for (int j = right; j >= 1; j--) {
    //         //     queue[j] = queue[j - 1];
    //         //     max = Math.max(max, queue[j]);
    //         // }
    //         //
    //         // queue[left] = nums[i];
    //         //
    //         // maxList[index] = max;
    //         // index++;
    //     }
    //     return maxList;
    // }
}
